1. Field of the Invention
The present invention relates to an error correction encoding and decoding system. More particularly, this invention is concerned with an error correction encoding and decoding system for producing a product code using inner codes and outer codes.
2. Related Background Art
When digital data transmission is performed to, for example, record or reproduce digital data on or from a magnetic recording medium, low-frequency components of digital codes to be recorded or transmitted on or to a magnetic recording medium or a transmission line must be suppressed. One of the suppressing methods is n-to-m conversion in which n-bit data is converted into m-bit (m&gt;n) data having less low-frequency components. This method, however, increases redundancy and the amount of transmission data.
Mapping encoding, for example, does not increase redundancy. The mapping encoding method can apply to image data or other data whose codes are closely correlated. This method is based on a characteristic that differential signals produced by performing differential encoding on input codes tend to concentrate in the vicinity of a zero level. To be more specific, the differential signals around the zero level are converted into codes of small digital sum values (hereafter, DSV), and thus low-frequency components of the code array are suppressed. 4-to-4 mapping encoding, for example, converts 4-bit differential codes into 4-bit codes.
The mapping encoding uses the correlations among code arrays. Therefore, low-frequency components of codes that are not correlated cannot be suppressed. Error-detecting codes or error-correcting codes are not correlated to one another, in general. Therefore, the low-frequency components of a code array made up of information codes and error-detecting or correcting codes for the information codes are suppressed less efficiently. This results in a high decoding error rate.
FIG. 1 shows an example of a data frame structure for transmitting a code array. The information data area contains mapped codes. To the inner code area, check points (error-correcting codes) of hamming codes or Lead Solomon codes are allocated. FIG. 2 shows a configuration of a data matrix in which data frames, one of which is shown in FIG. 1, are arranged lengthwise and a check point (outer code) is also allocated longitudinally. The data matrix is represented as a product code whose size is provided as a product of transverse codes by longitudinal codes. This matrix has check codes arranged two-dimensionally, which, therefore, is suitable for treating image data and other two-dimensional data.
However, assuming that data frames in the data matrix shown in FIG. 2 are to be transmitted sequentially, when inner codes continue, mapping encoding cannot suppress low-frequency components because of no correlations.
In particular, when it comes to transmitting a data frame made up of only check points of outer and inner codes, check points continue for a long time. This deteriorates the efficiency of suppressing low-frequency components markedly.
The present applicant invented a method of scattering check points of data frames among information codes as shown in FIG. 3, and disclosed the invention in U.S. Pat. No. 4,779,276. As for outer codes forming a product code, the applicant invented a method of re-arranging outer codes produced from columns of a data matrix into rows of the data matrix, then transmitting the outer codes in rows.
However, the former method does not care about outer codes of a product code shown in FIG. 2. The low-frequency components of a data frame made up of only check points of outer and inner codes are not suppressed very efficiently. The latter method has solved this problem. However, an outer code generating mode must be varied in columns, and an outer code encoding start point must also be altered in columns. In particular, when many check points of outer codes are generated, a pattern in which outer code check points do not continue transversely must be selected. Thus, the latter method requires complex processing.
Under these circumstances, the present applicant filed U.S. patent application Ser. No. 491,812 on Mar. 12, 1990 to propose the method below. A data matrix for transmitting data in the order shown in FIG. 4 is scanned as indicated with arrows in FIG. 5 to extract information codes (data) for generating outer codes, then the outer code check points are generated. As disclosed in U.S. Pat. No. 4,779,276, when reference row manipulation is performed on the rows and columns of a check matrix for generating check points, outer code check points can be scattered within a two-dimensional array in memory as shown in FIG. 6. In FIG. 6, outer codes are arranged obliquely. Thus, a data matrix with outer codes thus appended is scanned transversely (in rows), then data is sent to succeeding rows. Thereby, outer code check points are scattered on a time base.
FIG. 7 is a block diagram showing an example of a configuration of a code transmitting system that performs encoding based on oblique scanning shown in FIG. 5. In FIG. 7, 10 denotes an input terminal for inputting information (for example, image signals ) to be recorded. A mapping encoding circuit 12 establishes the correlations among information entered at the input terminal 10 and suppresses low-frequencies of the information. The data whose low-frequencies are suppressed by the circuit 12 is written in a memory 14 to create a data matrix. Information codes of the data matrix stored in the memory 14 are read out obliquely as shown in FIG. 5 under the control of an address control circuit 16, then applied to an outer code encoding circuit 18. The outer code encoding circuit 18 generates outer codes. The generated outer code parity bits are written at predetermined locations in the data matrix in the memory 14. The data matrix in the memory 14 are read transversely, then the read data is applied to an inner code encoding circuit 20. The inner code encoding circuit 20 produces inner code parity bits, and applies the parity bits to a synchronism addition circuit 22. The synchronism addition circuit 22 appends synchronization codes to the data. A recording circuit 24 records outputs of the synchronism addition circuit 22 on a magnetic tape, a magnetic or optical disk, or other recording medium.
Here, computation for parity bit generation will be explained briefly. Codes for which a parity bit is generated or M-symboled main information codes are regarded as a matrix I. The matrix I is represented as follows: EQU I=(i.sub.1, i.sub.2, i.sub.3, . . . i.sub.M)
Then, an error-detecting/correcting code word X is represented as follows: EQU X=(i.sub.1, i.sub.2, i.sub.3, - - -, i.sub.M, x.sub.1, x.sub.2, x.sub.3, - - -, x.sub.k)
where, x.sub.1 to x.sub.k represent parity bits. I and X are conditioned as X=I.multidot.G, wherein G represents a generation matrix of M rows by (M+K) columns. This matrix computation provides outer codes or parity bits x.sub.1 to x.sub.k. The generation matrix G is given by the expression (1), wherein the first to M-th columns whose diagonal elements are ls form a reference matrix and the (M+1)-th to (M+K)-th columns form a matrix of elements P.sub.i,j. ##EQU1##
FIG. 8 is a block diagram showing an example of a configuration of a parity calculating circuit that executes matrix computation X=I.multidot.G. A generation matrix ROM 11 contains elements P.sub.i,j of a generation matrix G at addresses associated with elements of information I read from a memory 14, inputs column and row addresses an address control circuit 16 generates via a terminal 9, then outputs coefficients for the corresponding elements P.sub.i,j. A Galois field multiplier 13 multiplier the elements P.sub.i,j retrieved from the generation matrix ROM 11 by the element of the information I to produce a Galois field. An adder 15 and a delay circuit 17 accumulate outputs of the Galois field multiplier 13. Thus, matrix computation is completed. Herein, Galois field addition pertains to EXCLUSIVE-OR in bits.
As described previously, a data matrix of information codes is scanned obliquely to extract the information codes for producing error-correcting code words. Then, parity check codes are produced. When the parity check codes are appended to a data matrix of information codes row by row, no data frame includes only parity check codes of outer and inner codes. Therefore, low-frequency components are suppressed efficiently.
The above procedure is easier than a procedure in which outer codes are generated in columns of a data matrix of information codes and appended transversely.
However, since information codes are extracted obliquely, an access address for accessing a memory 14 must be varied transversely and longitudinally according to a predetermined program. Furthermore, an address for accessing a generation matrix ROM 11 must also be varied transversely and longitudinally. This disables high-speed processing.
To be more specific, an outer code encoding circuit 18 must repeat a sequence of operations; reading information codes from the memory 14, generating outer codes, then writing the generated outer codes (and read information codes) in the memory 14, and thus complete a whole data matrix. Therefore, a memory of high accessibility must be used.
As described previously, information is scanned obliquely with respect to a direction of data transmission to generate outer codes. Therefore, row addresses or addresses pointing to transverse locations of information data in a matrix shown in FIG. 5, and column addresses or addresses pointing to longitudinal locations of information data in the matrix are required to read elements P.sub.i,j from a generation matrix ROM 11. Furthermore, generation matrix coefficients necessary for calculating outer codes differ with a generation matrix. Therefore, the generation matrix ROM 11 must have a very large capacity. For example, in a data matrix shown in FIG. 9, assuming that the first information code array I.sub.1 is represented as: EQU I.sub.1 =(i.sub.1,1 i.sub.2,1 i.sub.3,1 - - - i.sub.M,1)
and an error-correcting code word for the first information code array I.sub.1 is X.sub.1, and that the second information code array 12 is represented as: EQU I.sub.2 =(i.sub.1,2 i.sub.2,2 i.sub.3,2 i.sub.4,2 - - - i.sub.M,2)
and an error-correcting code word for the second information code array I.sub.2 is X.sub.2, X.sub.1 and X.sub.2 are provided by the expressions (2) and (3) below. ##EQU2## When the error-correcting code word X.sub.2 is generated, data is read from the data matrix in an order different from a transmission order. Thus, information data I.sub.2 is extracted.
In encoding based on oblique scanning, a complex manipulation is required to convert calculated error locations into column and row addresses of information data during decoding.